Packet Networks such as Internet Protocol (IP) networks or Ethernet networks typically operate on a “Best Efforts” basis. This means that they usually forward their data units or packets quickly across the network, but may occasionally experience congestion when they receive more packets than can be forwarded quickly. In this case they typically delay or drop excess packets, which may cause inconvenience to the senders or receivers of the packets.
Techniques have been developed to provide a more discriminating forwarding behaviour by, for example, giving some packets priority, or higher priority than others, based for example on which of a number of different traffic classes they are identified as belonging to, or on their source or intended destination. Such techniques typically need to be complemented by mechanisms such as Admission Control mechanisms which may be used to control the rate at which the high (or higher) priority packets enter the network, in order to prevent them from being able to congest or monopolise the resources of the network to the extent that they completely exclude packets having lower priority from the network. By appropriate use of such mechanisms and appropriate configuration, the resources available to the network may effectively be partitioned in such a way as to ensure that the network will not accept higher priority packets at a higher rate than the rate at which the network can actually guarantee to provide such packets with priority treatment, while also ensuring that packets having lower priority can not be completely excluded.
Other schemes for controlling congestion rely on the network providing a signal to the senders or receivers of packets when congestion is experienced allowing them to “back-off”, i.e. to reduce the rate at which packets are being sent and thereby alleviating the congestion.
Recent approaches to managing congestion in the Internet and other networks require routers (or switches) in the network to perform Active Queue Management and to signal congestion using some marking scheme. The router chooses a proportion of the packets being forwarded based on its current congestion level and then marks them with a congestion mark typically using a protocol such as ECN (RFC 2481—A Proposal to add Explicit Congestion Notification (ECN) to IP). If the router is uncongested then very few packets will be marked. If the router is congested many (or all) packets will be marked.
With reference to FIG. 1, an overview of a generalised network element, such as a router or switch, is shown. Flows of packets arrive at the network element from other nodes in a network via one or more network interfaces, and are presented for onward transmission to other nodes in the network via another network interface. If the network element is performing a packet marking process to indicate congestion, a packet-marking means is present at the network element or one or more of its network interfaces.
Existing mechanisms for marking packets are typically based upon inspecting the real queue of packets at the router (or switch) interface and marking the packets if this queue is long. An example of such an approach is given in “Random Early Marking: An Optimization Approach to Internet Congestion Control” by David Lapsley and Steven Low (Proceedings of the 7th IEEE International Conference on Networks, 28 Sep.-1 Oct., 1999). Such techniques are not difficult to implement with current switches and routers. However, they are not entirely satisfactory because they do not start to signal congestion until the real queue starts to grow in size. It is preferable to generally operate the network so that real queues very seldom grow in size since long queues mean increased latency and packet loss. Thus it would be better if the marking mechanism could start marking in the presence of imminent congestion before the real queue start to grow.
Virtual Queue Marking
An example of such early marking is being standardised in the IETF PCN Working Group (http://www.ietf.org/html.charters/pcn-charter.html), where PCN refers to “Pre-Congestion Notification”. This working group is trying to standardise a marking mechanism based on looking at how the arrival rate of packets compares not to the line rate (as the real queue does) but instead to a slightly reduced rate. This “virtual queue” experiences congestion before the real queue does and hence can provide more timely congestion signals. An academic discussion of the advantages of such a mechanism is given in “Resource pricing and the evolution of congestion control” by R. J. Gibbens and F. P. Kelly (Automatica 35, 1999). Virtual queues were first proposed in a different form (and for use in ATM networks) in “Buffer Overflow Asymptotics for a Switch Handling Many Traffic Sources” by Costas Courcoubetis and Richard Weber (Journal of Applied Probability 33, pages 886-903, 1996). The precise form discussed here was proposed by Kunniyur and Srikant in “Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management” (Proc. ACM SIGCOMM'01, Computer Communication Review 31 (4), October 2001).
It will be noted that the term “virtual queue” is also used in switch and router hardware design to denote a virtual queue on an ingress interface that tracks the queue on an egress interface, but this has no relation to the virtual queue discussed here.
Virtual Queue Marking (VQM) defines a strategy—to be implemented on network interfaces—to mark packets of a packet-switched network with a signal expressing the state of congestion of that interface. This packet marking strategy is based on a congestion measurement defined by a virtual queue. A virtual queue is a conceptual queue that is actually simply a single variable recording the length of the virtual queue, where the lengths of packets are added to it as they arrive while some fraction of the line rate of that interface is subtracted at the same time. This means that an interface's virtual queue builds up more rapidly than its real queue.
FIG. 2 shows a model illustrating a Virtual Queue Marking (VQM) process. As each new packet arrives and is added to the real queue, the size of the virtual queue is incremented by the number of bytes in the new packet. If packets are able to be presented for onward transmission to other nodes in the network at a rate of X bytes per second (bps), the virtual queue is decremented at a rate of θX bps, where θ<1.
The size of the virtual queue is then used to decide whether or not to send a congestion signal (i.e. a signal expressing a state of congestion for that interface). Typically we would wish to send a congestion signal if the size of the virtual queue exceeds some threshold. There are several ways of coding a congestion signal; a desirable way is to ‘mark’ a packet, by setting a bit in the packet header to 1 if the signal is ‘congested interface’, or to 0 if the signal is ‘uncongested interface’. Another possible way of using the measurement of congestion that the virtual queue provides, rather than marking packets, is to send an alert to a management system. Alternatively, but less desirably, the traffic class of the real packet may be re-marked, or the real packet might be dropped or re-routed.
Token-Bucket Marking
There are compelling reasons to desire the implementation of a virtual queue marker in real routers and switches but current routers typically cannot support such a marker. They typically only provide support for marking based on the size of the real queue.
However, the hardware that routers use is often provided with additional capabilities, that are used to police traffic flows (or some particular subset of the router traffic) to some configured rate lower than the line rate. These capabilities use a marking mechanism that sees the traffic in this subset and then marks it (typically not with an ECN mark but in some other way, such as changing the Differentiated Services Code Point (DSCP) of the packet). Since these marking mechanisms are configurable to operate at a lower rate than the line rate, they could provide support for a virtual queue. However, these markers typically do not use the discipline used for a virtual queue. Typically they are based on what are referred to as token buckets (or leaky buckets) which mark packets when they become empty.
A typical such marking mechanism is to use a token bucket, as indicated by FIG. 3, which shows a model illustrating a Token Bucket Marking (TBM) process. The token bucket B is (notionally) filled with tokens at a configured rate (the Committed Information Rate or CIR), and is emptied of tokens as packets arrive. Again, if packets are able to be presented for onward transmission at a rate of X bps, the virtual queue is decremented at a rate of θX bps, where θ<1. C indicates the maximum number of tokens which can be in the token bucket, and Tc=current number of tokens in bucket. A packet marker marks packets according to a predetermined token consumption and packet marking algorithm before presenting the packets for onward transmission.
Thus this appears similar to a virtual queue operating upside-down. However, the core difference is that it only marks packets while it is empty of tokens. In contrast, a virtual queue will typically mark whenever it is above a threshold which is well away from the end of the queue. The token bucket would achieve the same behaviour only if it marked whenever its level fell below a threshold configured well above its empty point. However, to implement a virtual queue in hardware requires additional registers and is a non-trivial change to the implementation of a token bucket.
Virtual Queue Vs. Token Bucket Marking
Using a token bucket in this way then results in a marking mechanism which has less memory than a virtual queue: following a burst of packets, the token bucket quickly stops marking whereas the virtual queue continues to mark until the real queue has had time to drain back to empty. A virtual queue thus marks as much traffic as there was in the burst since marking started, which more accurately reflects the impact the packet stream is having on the real queue, and is thus preferred as a congestion marking mechanism. This is termed “marking symmetry”, which is preferred because the amount of marking accurately reflects the economic cost of the congestion caused, so markings may then be used as an accounting metric and not just as a control signal.
Routers and switches often, as well as providing simple token buckets, also provide for a marking mechanism called Single Rate Three Colour Marking (IETF RFC 2697—srTCM). For example, many router and switch manufacturers use the Broadcom 56510 chipset for queue management, which includes a hardware implementation of srTCM marking. Further information about the Broadcom 56510 chipset is available from Product Brief BCM56510 at www.broadcom.com/collateral/pb/56510-PB00-R.pdf, or from Broadcom Corporation, 16215 Alton Parkway, Irvine, Calif., US.
The srTCM mechanism is modelled as involving two token buckets, B1 and B2, as depicted in FIG. 4. The level of tokens in buckets B1 and B2 are respectively TC and TE, and the maximum number of tokens in the buckets are C and E.
The srTCM mechanism aims to mark packets with one of three states often termed “green”, “yellow” and “red”. The Committed Information Rate (CIR) is the rate at which tokens are pushed into the bucket, and this corresponds to a traffic rate below which all packets are expected to be marked green. The Committed Burst Size (CBS) is the size of bucket B1 (i.e. this is C), which corresponds to the maximum size of the burst which will not cause any yellow (or red) marking. The Excess Burst Size (EBS) is the size of bucket B2 (i.e. this is E), which corresponds to the maximum size of the burst which will not cause yellow marking to go into red marking.
There are two main algorithms defined by srTCM: the way tokens fill the two buckets, and the way tokens are consumed by packets.
Token Consumption and Packet Marking Algorithm
Every time a packet of size B arrives, the srTCM marker performs the marking algorithm in order to perform the following steps:
if (TC > B) then mark packet green TC = TC − Belse if (TE > B) then mark packet yellow TE = TE − Belse mark packet red
In practice token consumption algorithms may also handle cases where the fill of a bucket is less than packet size B, typically by emptying the bucket to zero and if necessary removing the remainder from the other bucket. Other implementations allow the bucket to go slightly negative. Such detail has been omitted here to emphasise the primary intent of the algorithm.
Token Filling Algorithm
The two token buckets are filled at a specified committed information rate R by a single source of tokens according to the following algorithm invoked repeatedly every F/R seconds:
if (TC < C) then increase TC by Felse if (TE < E) then increase TE by F
Equivalently, the following fill algorithm may be triggered by each packet arrival event, rather than regular timer events:
t_now := now( )F := R(t_now − t_previous)if (TC < C) then increase TC by Felse if (TE < E) then increase TE by Ft_previous := now( )
Virtual Queue Marking is simple to implement in software, but there are currently no hardware implementations of it, at least not on low-end, general purpose hardware. It will be understood that hardware implementation (rather than software implementation) is advantageous for high speed, simple operation. Current routers and switches typically implement three alternative mechanisms to make measurements at network interfaces: token bucket marking (TBM), Single Rate Three Colour Marking (srTCM), and Two Rate Three Colour Marking (trTCM).
It will be understood that TBM could be modified to behave identically to VQM by adding a threshold to the token bucket (a threshold above which the marker starts marking). Unfortunately this is a route that involves considerable re-design of the hardware, however.
Instead, srTCM inherently introduces a mechanism that uses two token buckets. Although the point of the two buckets (in srTCM as it is) is to allow for exceeding tokens from bucket B1 to overflow into B2, the inventors have realised that by modifying the algorithm through which tokens are pushed into the buckets, it is possible to use the size of one bucket as the threshold of a virtual queue.
Referring to prior art patent publications, U.S. Pat. No. 6,970,426, which could be considered to be of background relevance, relates generally to the field of data communications, and in particular to a device metering a received data stream and marking packets in the data stream differently, for example, based on one factor, or a combination of one or more factors, such as packet rate, packet length, time of arrival of a packet in the data stream, etc. A packet may be marked, and remarked, for example, to indicate a level of assurance as to whether the packet is forwarded or discarded.
European patent application EP 1,694,004 relates to a network device for processing data in a network, and in particular to a process of controlling the flow of data through the network device that is said to allow for enhanced processing speeds and expandability. Use of the above for programmable colour marking, as well bucket incrementing and decrementing, is discussed, and in particular versions, the use of programmable registers to implement the srTCM and the trTCM methods is discussed.
Referring to the academic literature, a more recent paper by Kunniyur & Srikant: “An Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management” (IEEE/ACM Transactions on Networking, Vol. 12, No. 2, April 2004), which could also be considered to be of background relevance, studies the properties of virtual queues, and considers a particular scheme, referred to as the Adaptive Virtual Queue (AVQ). A discussion is included of how the AVQ may be implemented as a simple token bucket using only a few lines of code.